#include <pmm.h>
#include <list.h>
#include <string.h>
extern const struct pmm_manager buddy_pmm_manager;
free_area_t free_area;

#define free_list (free_area.free_list)
#define nr_free (free_area.nr_free)


size_t get_power_of2(size_t x)
{
    size_t power = 0;
    while (x > 1) {
        x >>= 1;
        power++;
    }
    return (size_t)1 << power;
}



static void
buddy_init(void)
{
    list_init(&free_list);
    nr_free = 0;
}

static void
buddy_init_memmap(struct Page *base, size_t n)
{

    assert(n > 0);
    struct Page *p = base;
    for (; p != base + n; p++)
    {
        assert(PageReserved(p));
        p->flags = p->property = 0;
        set_page_ref(p, 0);
    }

    nr_free += n;
    base += n;
    while (n != 0)
    {
        size_t curr_n = get_power_of2(n);
        base -= curr_n;
        base->property = curr_n;
        SetPageProperty(base);
        list_entry_t *le;
        for (le = list_next(&free_list); le != &free_list; le = list_next(le))
        {
            struct Page *p = le2page(le, page_link);
            if ((p->property > base->property) || (p->property == base->property && p > base))
                break;
        }
        list_add_before(le, &(base->page_link));

        n -= curr_n;
    }
}

static struct Page *
buddy_alloc_pages(size_t n)
{
    assert(n > 0);
    struct Page *page = NULL;
    size_t power = get_power_of2(n);
    if (power < n)
        n = 2 * power;
    if (n > nr_free)
    {
        return NULL;
    }
    else
    {

        list_entry_t *le = &free_list;
        while ((le = list_next(le)) != &free_list)
        {
            struct Page *p = le2page(le, page_link);
            if (p->property >= n)
            {
                page = p;
                break;
            }
        }
        if (page != NULL)
        {
            while (n < page->property)
            {
                unsigned int temp = page->property /= 2;

                struct Page *page_a, *page_b;
                page_a = page;
                page_b = page + temp;
                page_a->property = temp;
                page_b->property = temp;
                SetPageProperty(page_a);
                SetPageProperty(page_b);
                list_add_after(&(page->page_link), &(page_b->page_link));
            }
            nr_free -= n;
            ClearPageProperty(page);
            assert(page->property == n);
            list_del(&(page->page_link));
        }
    }
    return page;
}

static void
buddy_free_pages(struct Page *base, size_t n)
{
    assert(n > 0);
    size_t power = get_power_of2(n);
    if (power< n)
        n = 2 * power;
    struct Page *p = base;
    for (; p != base + n; p++)
    {
        assert(!PageReserved(p) && !PageProperty(p));
        p->flags = 0;
        set_page_ref(p, 0);
    }
    base->property = n;
    SetPageProperty(base);
    nr_free += n;
    list_entry_t *le;
    for (le = list_next(&free_list); le != &free_list; le = list_next(le))
    {
        p = le2page(le, page_link);
        if ((base->property < p->property) || (p->property == base->property && p > base))
        {
            break;
        }
    }
    list_add_before(le, &(base->page_link));
    if (p->property == base->property)
    {
        unsigned int freenum = p->property;
        if (p + freenum == base)
        {
            p->property += base->property;
            ClearPageProperty(base);
            list_del(&(base->page_link));
            le = &(p->page_link);
            base = p;
        }
    }

    for (; le != &free_list; le = list_next(le))
    {
        struct Page *tmp = le2page(le, page_link);
        unsigned int freenum = tmp->property;
        if (tmp->property == base->property)
        {
            if (base + freenum == tmp)
            {
                base->property += freenum;
                ClearPageProperty(tmp);
                list_del(&(tmp->page_link));
                le = &(base->page_link);
            }
        }
        if (tmp->property > base->property)
        {
            list_entry_t *next = list_next(&(base->page_link));
            struct Page *nextpage = le2page(next, page_link);
            unsigned int nextpage_num = 0, basenum = base->property;
            for (; nextpage->property < base->property; next = list_next(next))
            {
                nextpage_num++;
            }
            if (next != list_next(&base->page_link))
            {
                list_del(&(base->page_link));
                list_add_before(next, &(base->page_link));
            }
            break;
        }
    }
}

static void
basic_check(void)
{
    struct Page *p0, *p1, *p2;
    p0 = p1 = p2 = NULL;
    assert((p0 = alloc_page()) != NULL);
    assert((p1 = alloc_page()) != NULL);
    assert((p2 = alloc_page()) != NULL);

    assert(p0 != p1 && p0 != p2 && p1 != p2);
    assert(page_ref(p0) == 0 && page_ref(p1) == 0 && page_ref(p2) == 0);

    assert(page2pa(p0) < npage * PGSIZE);
    assert(page2pa(p1) < npage * PGSIZE);
    assert(page2pa(p2) < npage * PGSIZE);

    list_entry_t free_list_store = free_list;
    list_init(&free_list);
    assert(list_empty(&free_list));

    unsigned int nr_free_store = nr_free;
    nr_free = 0;

    assert(alloc_page() == NULL);

    free_page(p0);
    free_page(p1);
    free_page(p2);
    assert(nr_free == 3);

    assert((p0 = alloc_page()) != NULL);
    assert((p1 = alloc_page()) != NULL);
    assert((p2 = alloc_page()) != NULL);

    assert(alloc_page() == NULL);

    free_page(p0);
    assert(!list_empty(&free_list));

    struct Page *p;
    assert((p = alloc_page()) == p0);
    assert(alloc_page() == NULL);

    assert(nr_free == 0);
    free_list = free_list_store;
    nr_free = nr_free_store;

    free_page(p);
    free_page(p1);
    free_page(p2);
}

static void
buddy_check(void)
{
    int count = 0, total = 0;
    list_entry_t *le = &free_list;
    while ((le = list_next(le)) != &free_list)
    {
        struct Page *p = le2page(le, page_link);
        assert(PageProperty(p));
        count++, total += p->property;
    }
    assert(total == nr_free_pages());

    basic_check();

    
    struct Page *p0 = alloc_pages(26), *p1;
    assert(p0 != NULL);
    assert(!PageProperty(p0));

    list_entry_t free_list_store = free_list;
    list_init(&free_list);
    assert(list_empty(&free_list));
    assert(alloc_page() == NULL);

    unsigned int nr_free_store = nr_free;
    nr_free = 0;
    //.........................................................
    // 先释放
    free_pages(p0, 26); // 32+  (-:已分配 +: 已释放)
    // 首先检查是否对齐2
    p0 = alloc_pages(6);  // 8- 8+ 16+
    p1 = alloc_pages(10); // 8- 8+ 16-
    assert((p0 + 8)->property == 8);
    free_pages(p1, 10); // 8- 8+ 16+
    assert((p0 + 8)->property == 8);
    assert(p1->property == 16);
    p1 = alloc_pages(16); // 8- 8+ 16-
    // 之后检查合并
    free_pages(p0, 6); // 16+ 16-
    assert(p0->property == 16);
    free_pages(p1, 16); // 32+
    assert(p0->property == 32);

    p0 = alloc_pages(8); // 8- 8+ 16+
    p1 = alloc_pages(9); // 8- 8+ 16-
    free_pages(p1, 9);   // 8- 8+ 16+
    assert(p1->property == 16);
    assert((p0 + 8)->property == 8);
    free_pages(p0, 8); // 32+
    assert(p0->property == 32);
    // 检测链表顺序是否按照块的大小排序的
    p0 = alloc_pages(5);
    p1 = alloc_pages(16);
    free_pages(p1, 16);
    assert(list_next(&(free_list)) == &((p1 - 8)->page_link));
    free_pages(p0, 5);
    assert(list_next(&(free_list)) == &(p0->page_link));

    p0 = alloc_pages(5);
    p1 = alloc_pages(16);
    free_pages(p0, 5);
    assert(list_next(&(free_list)) == &(p0->page_link));
    free_pages(p1, 16);
    assert(list_next(&(free_list)) == &(p0->page_link));

    // 还原
    p0 = alloc_pages(26);
    //.........................................................
    assert(nr_free == 0);
    nr_free = nr_free_store;

    free_list = free_list_store;
    free_pages(p0, 26);

    le = &free_list;
    while ((le = list_next(le)) != &free_list)
    {
        assert(le->next->prev == le && le->prev->next == le);
        struct Page *p = le2page(le, page_link);
        count--, total -= p->property;
    }
    assert(count == 0);
    assert(total == 0);
}

static size_t
buddy_nr_free_pages(void)
{
    return nr_free;
}

const struct pmm_manager buddy_pmm_manager = {
    .name = "buddy_pmm_manager",
    .init = buddy_init,
    .init_memmap = buddy_init_memmap,
    .alloc_pages = buddy_alloc_pages,
    .free_pages = buddy_free_pages,
    .nr_free_pages = buddy_nr_free_pages,
    .check = buddy_check,
};